package com.copy;

import java.util.HashMap;
import java.util.Map;

/**
 * 题：复制带随机指针的链表
 *
 * 给你一个长度为 n 的链表，每个节点包含一个额外增加的随机指针 random ，该指针可以指向链表中的任何节点或空节点。
 *
 * 构造这个链表的 深拷贝。 深拷贝应该正好由 n 个 全新 节点组成，其中每个新节点的值都设为其对应的原节点的值。新节点的 next 指针和 random 指针也都应指向复制链表中的新节点，并使原链表和复制链表中的这些指针能够表示相同的链表状态。复制链表中的指针都不应指向原链表中的节点 。
 *
 * 例如，如果原链表中有 X 和 Y 两个节点，其中 X.random --> Y 。那么在复制链表中对应的两个节点 x 和 y ，同样有 x.random --> y 。
 *
 * 返回复制链表的头节点。
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode.cn/problems/copy-list-with-random-pointer
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
public class CopyRandomPointer1 {

    public Node copyRandomList(Node head) {
        if (head == null) return head;

        Map<Node, Node> map = new HashMap<>();
        Node newHead = head;
        Node dummy = new Node(-1);

        while (newHead != null) {
            Node newNode;
            if (!map.containsKey(newHead)) {
                newNode = new Node(newHead.val);
                map.put(newHead, newNode);
            } else {
                newNode = map.get(newHead);
            }
            dummy.next = newNode;
            if (newHead.random != null) {
                Node random = newHead.random;
                if (map.containsKey(random)) {
                    Node copyRandom = map.get(random);
                    newNode.random = copyRandom;
                } else {
                    Node copyRandom = new Node(random.val);
                    map.put(random, copyRandom);
                    newNode.random = copyRandom;
                }
            }
            dummy = newNode;
            newHead = newHead.next;
        }
        return map.get(head);
    }

    public Node copyRandomList2(Node head) {
        if (head == null) return head;

        Map<Node, Node> map = new HashMap<>();
        Node newHead = head;
        Node dummy = new Node(-1);

        while (newHead != null){
            Node newNode ;
            if(map.containsKey(newHead)){
                newNode = map.get(newHead);
            }else{
                newNode = new Node(newHead.val);
                map.put(newHead,newNode);
            }
            dummy.next = newNode;

            if(newHead.random != null){
                Node random = newHead.random;
                if(map.containsKey(random)){
                    newNode.random = map.get(random);
                }else{
                    Node newRandom = new Node(random.val);
                    map.put(random, newRandom);
                    newNode.random = newRandom;
                }
            }

            dummy = newNode;
            newHead = newHead.next;
        }

        return map.get(head);
    }
}
